package 二叉树高频题目_下_不含树型dp;

import java.util.Stack;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
public class Code05_ValidateBinarySearchTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public static int MAXN = 10001;
    // 使用数组表示栈
    public static TreeNode[] stack = new TreeNode[MAXN];
    // 栈顶/栈中元素的个数
    public static int top;
    // 搜索二叉树的中序遍历的结果的大小是递增的
    public static boolean isValidBST1(TreeNode root) {
        if(root == null){
            return true;
        }
        // cur当前节点的上一个节点，以便于和当前节点的值进行比较来判断是否是搜索二叉树
        TreeNode pre = null;
        TreeNode cur = root;
        top = 0;
        while(top > 0 || cur != null){
            if(cur != null){
                stack[top++] = cur;
                cur = cur.left;
            }else {
                cur = stack[--top];
                if(pre != null && pre.val >= cur.val){
                    return false;
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return true;
    }

    // 全局变量记录每个节点的左右子树的最小值和最大值
    public static long min;
    public static long max;
    public boolean isValidBST(TreeNode root) {
        // 空节点，最小值为long类型最大值，最大值为long类型最小值
        if(root == null){
            min = Long.MAX_VALUE;
            max = Long.MIN_VALUE;
            return true;
        }
        // lok 判断左子树是否是搜索二叉树
        boolean lok = isValidBST(root.left);
        // lmin,lmax 记录左子树的最小值和最大值
        long lmin = min;
        long lmax = max;
        // rok 判断右子树是否是搜索二叉树
        boolean rok = isValidBST(root.right);
        // rmin,rmax 记录右子树的最小值和最大值
        long rmin = min;
        long rmax = max;
        // 对当前节点根据左右子树的最大值和最小值得出当前节点的最大值和最小值
        min = Math.min(Math.min(lmin, rmin), root.val);
        max = Math.max(Math.max(lmax, rmax), root.val);
        // 搜索二叉树要满足左右子树都是搜索二叉树并且当前节点的值要大于左子树的最大值，小于右子树的最小值
        return lok && rok && root.val > lmax && root.val < rmin;
    }
}
